<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>min_qcost_flow</title>
  </head>
  <body bgcolor="#FFFFFF">
    <center>Scilab function</center>
    <div align="right">Last update : September 1995</div>
    <p>
      <b>min_qcost_flow</b> -  minimum quadratic cost flow</p>
    <h3>
      <font color="blue">Calling Sequence</font>
    </h3>
    <dl>
      <dd>
        <tt>[c,phi,flag] = min_qcost_flow(eps,g)  </tt>
      </dd>
    </dl>
    <h3>
      <font color="blue">Parameters</font>
    </h3>
    <ul>
      <li>
        <tt>
          <b>eps</b>
        </tt>: scalar, precision</li>
      <li>
        <tt>
          <b>g</b>
        </tt>: graph list</li>
      <li>
        <tt>
          <b>c</b>
        </tt>: value of cost</li>
      <li>
        <tt>
          <b>phi</b>
        </tt>: row vector of the value of flow on the arcs</li>
      <li>
        <tt>
          <b>flag</b>
        </tt>: feasible problem flag (0 or 1)</li>
    </ul>
    <h3>
      <font color="blue">Description</font>
    </h3>
    <p>
      <tt>
        <b>min_qcost_flow</b>
      </tt> computes the minimum quadratic cost flow in the network 
    <tt>
        <b>g</b>
      </tt>. It returns the total cost of the flows on the arcs <tt>
        <b>c</b>
      </tt> and
    the row vector of the flows on the arcs <tt>
        <b>phi</b>
      </tt>. <tt>
        <b>eps</b>
      </tt> is the precision
    of the iterative algorithm. If the problem is not feasible (impossible to 
    find a compatible flow for instance), <tt>
        <b>flag</b>
      </tt> is equal to 0, otherwise it 
    is equal to 1.</p>
    <p>
    The bounds of the flow are given by the elements <tt>
        <b>edge_min_cap</b>
      </tt> and
    <tt>
        <b>edge_max_cap</b>
      </tt> of the graph list. 
    The value of the maximum capacity must be greater than or equal to the 
    value of the minimum capacity.
    If the value of <tt>
        <b>edge_min_cap</b>
      </tt> or <tt>
        <b>edge_max_cap</b>
      </tt> is not given (empty
    row vector <tt>
        <b>[]</b>
      </tt>), it is assumed to be equal to 0 on each edge.</p>
    <p>
    The costs on the edges are given by the elements <tt>
        <b>edge_q_orig</b>
      </tt> and
    <tt>
        <b>edge_q_weight</b>
      </tt> of the graph list. The cost on arc <tt>
        <b>u</b>
      </tt> is given by:</p>
    <p>
      <tt>
        <b>(1/2)*edge_q_weight[u](phi[u]-edge_q_orig[u])^2</b>
      </tt>
    </p>
    <p>
    The costs must be non negative.
    If the value of <tt>
        <b>edge_q_orig</b>
      </tt> or <tt>
        <b>edge_q_weight</b>
      </tt> is not given (empty 
    row vector <tt>
        <b>[]</b>
      </tt>), it is assumed to be equal to 0 on each edge.</p>
    <p>
    This function uses an algorithm due to M. Minoux.</p>
    <h3>
      <font color="blue">Examples</font>
    </h3>
    <pre>

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10 1 8];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1 12 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
show_graph(g);
g1=g; ma=arc_number(g1);
rand('uniform');
while %T then
  g1('edge_min_cap')=round(5*rand(1,ma));
  g1('edge_max_cap')=round(20*rand(1,ma))+30*ones(1,ma);
  g1('edge_q_orig')=0*ones(1,ma);
  g1('edge_q_weight')=ones(1,ma);
  [c,phi,flag]=min_qcost_flow(0.001,g1);
 if flag==1 then break; end;
end;
x_message(['The cost is: '+string(c);
          'Showing the flow on the arcs']);
ii=find(phi&lt;&gt;0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
show_graph(g1);
 
  </pre>
    <h3>
      <font color="blue">See Also</font>
    </h3>
    <p>
      <a href="min_lcost_cflow.htm">
        <tt>
          <b>min_lcost_cflow</b>
        </tt>
      </a>,&nbsp;&nbsp;<a href="min_lcost_flow1.htm">
        <tt>
          <b>min_lcost_flow1</b>
        </tt>
      </a>,&nbsp;&nbsp;<a href="min_lcost_flow2.htm">
        <tt>
          <b>min_lcost_flow2</b>
        </tt>
      </a>,&nbsp;&nbsp;</p>
  </body>
</html>
